//二叉树

#pragma once

#include <iostream>

//二叉树的存储结构
template <typename E>
struct BiTNode
{
    E data;
    BiTNode *lchild, *rchild;
};

template <typename E>
using BiTree = BiTNode<E> *;


//先序遍历二叉树 T, 用 visit 访问每个结点
template <typename E, typename F>
void PreOrder(BiTree<E> T, F visit)
{
    if (T)
    {
        visit(T->data);
        PreOrder(T->lchild, visit);
        PreOrder(T->rchild, visit);
    }
}

//中序遍历二叉树 T, 用 visit 访问每个结点
template <typename E, typename F>
void InOrder(BiTree<E> T, F visit)
{
    if (T)
    {
        InOrder(T->lchild, visit);
        visit(T->data);
        InOrder(T->rchild, visit);
    }
}


//后序遍历二叉树 T, 用 visit 访问每个结点
template <typename E, typename F>
void PostOrder(BiTree<E> T, F visit)
{
    if (T)
    {
        PostOrder(T->lchild, visit);
        PostOrder(T->rchild, visit);
        visit(T->data);
    }
}

//求二叉树 T 中结点个数
template <typename E>
int NodeCount(BiTree<E> T)
{
    if(T == nullptr)
        return 0;
    int L = NodeCount(T->lchild);
    int R = NodeCount(T->rchild);
    return L + R + 1;
}

//求二叉树 T 中叶子结点数
template <typename E>
int LeafCount(BiTree<E> T)
{
    if(T == nullptr)
        return 0;
    if(T->lchild == nullptr && T->rchild == nullptr)
        return 1;
    int L = LeafCount(T->lchild);
    int R = LeafCount(T->rchild);
    return L + R;
}

//求二叉树 T 的深度
template <typename E>
int Depth(BiTree<E> T)
{
    if(T == nullptr)
        return 0; 
    int L = Depth(T->lchild);
    int R = Depth(T->rchild);
    return L > R ? L + 1 : R + 1;
}

//打印二叉树 T (逆时针旋转 90 度)
template <typename E>
void PrintBinaryTree(BiTree<E> T, int level)
{
    if(T == nullptr)
        return; 
    PrintBinaryTree(T->rchild, level + 1); //打印右子树
    for(int i = 0; i < level; i++)
        std::cout << "   ";
    std::cout << T->data << std::endl;
    PrintBinaryTree(T->lchild, level + 1); //打印左子树
}

template <typename E>
void PrintBinaryTree(BiTree<E> T)
{
    PrintBinaryTree(T, 0);
}

//根据先序序列创建二叉树
void CreatBinaryTree(BiTree<char> &T)
{
    char c;
    std::cin >> std::noskipws >> c; //noskipws 不跳过空白字符
    if(c == ' ')
        T = nullptr;
    else
    {
        T = new BiTNode<char>;
        T->data = c;
        CreatBinaryTree(T->lchild);
        CreatBinaryTree(T->rchild);
    }
    
}